NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part2/17685

Internet Message Format | 1996-08-05 | 5.6 KB

Path: newsfeed.concentric.net!news
From: "Alan L. Lovejoy" <[e-mail]>
Newsgroups: comp.lang.java,comp.lang.c++,comp.lang.smalltalk
Subject: Re: Will Java kill C++?
Date: Wed, 17 Apr 1996 00:03:51 -0700
Organization: Modulation
Message-ID: <[e-mail]>
References: <[e-mail]> <4kbfn8$[e-mail]> <4kqjf6$[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: cnc009035.concentric.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 2.01Gold (Win95; U)

Carl Laurence Gonsalves wrote:
>
> In article <[e-mail]>,
> Alan L. Lovejoy <[e-mail]> wrote:
> >Mike Zorn wrote:
> >>
> >> In <4kbfn8$[e-mail]> [e-mail] (Mark VanTassel) writes:
> >>
> >> >"Alan L. Lovejoy" <[e-mail]> wrote:
> >> >>Bzzzt!  Not according to the benchmarks I've done.  Go benchmark the factorial or fibonacci
> >> >>functions (implemented recursively) in both C and a good Smalltalk.  You are in for a big
> >> >>surprise.
> >
> >> >I don't think this is a valid benchmark... (and I too fail to see how
> >> >Smalltalk can be faster than C++ except perhaps in bizarre special
> >> >cases)
> >>    True, the Fibonacci and factorial are not good candidates for a
> >> recursive algorithm.  (They're just taught that way because it's one
> >> of the few recursive problems that we can understand in first-year
> >> college courses.)
> >>    On the other hand, almost any interesting program, compiled & run
> >> in different languages, should be able to give a good idea of how the
> >> languages compare.  For my part, I'd also like to look at the source
> >> code, and know how long it took to write (and debug) the two programs.
> >>    So, Alan, I guess you'll have to come up with a program for
> >> Ackermann's Function in C++ and Smalltalk to satisfy the rest of us.
> >>
> >> Mike Zorn      [e-mail]   |  Thought for the day:
> >>   http://www.kaiwan.com/~ozma/   |    Java is C--
> >
> >I did those benchmars to prove that Smalltalk message sends are faster
> >than c function calls.  To do that, I needed a benchmark that consisted
> >mostly of function calls/message sends--and involved as little other
> >code as possible.  The recursive factorial and fibonacci functions
> >meet those requirements better than anything else I could think of.
>
> Both factorial and fibonacci are tail-recursive, which means that your
> translator may be doing tail recursion elimination, folding your n message
> sends (or function calls) down to one (plus a loop).
>
> I don't know of any C compilers that do tail recursion elimination. I
> don't know enough about the workings of Smalltalk to say for sure, but it
> may be possible that your translator is doing tail recursion elimination,
> thereby making message sends seem to be a heck of a lot more efficient
> than they really are.
>
> Try doing a similar test with functions that aren't tail-recursive. Or at
> least find out if your Smalltalk translator may be doing tail-recursion
> elimination.
>
> --
>         Carl Laurence Gonsalves - [e-mail]
>                    Computer Science, University of Waterloo
>                http://www.undergrad.math.uwaterloo.ca/~clgonsal/
>                    http://www.csclub.uwaterloo.ca/~clgonsal/

Here's the Smalltalk method source code:

factorial
    "Answer the factorial of the receiver. Fail if the
    receiver is less than 0."

    self < 2
        ifTrue:
            [self < 0 ifTrue: [self error: 'Must not be negative'].
            ^1].
    ^(self - 1) factorial * self

Here's the bytecodes for the same method:

1 <44> push self
2 <4B> push 2
3 <A2> send <
4 <E8 0B> jump false 17
6 <44> push self
7 <49> push 0
8 <A2> send <
9 <C4> jump false 15
10 <44> push self
11 <1C> push 'Must not be negative'
12 <F0 20> send error:
14 <66> pop
15 <4A> push 1
16 <65> return
17 <44> push self
18 <4A> push 1
19 <A1> send -
20 <71> send factorial
21 <44> push self
22 <A8> send *
23 <65> return

I see no tail recursion elimination.  It's harder to do in Smalltalk, because
any message send could theoretically add, recompile, or remove any method to,
in or from any class. Message semantics (with some very specific exceptions that
have no bearing here) is NOT defined by the Smalltalk syntax.

Also, note that the main logic sequence executes 4 message sends out of 11
instructions--a rather high ratio for C-code (equating message sends with
function calls, of course), but typical for Smalltalk.

What speeds things up is that the bytecodes for each method executed are translated
once into native code, stored in a native method cache, and then directly executed
the next time the same method is executed.  And when the 'factorial' message is
sent (for example), message selector to method lookup starts by checking whether the
class of the message receiver is the same as the last time that message was sent to
that receiver (where "same receiver" is determined lexically).  If so, it can jump
straight to the correct method. And I do mean "JMP," not "JSR."  So on machines with
high "JSR" overhead, such as the SPARC I did my benchmarks on, Smalltalk is actually
faster than C.  This is a reproducible fact.

Because of 32-bit overflow (a problem for C, not Smalltalk), the benchmark consists of
computing the factorial of 12 (=479,001,600) a large number of times (so that execution
time is about 1 minute).  The time to simply execute an empty loop the same number of
times is subtracted from the overall time, so that only the time actually spent computing
the factorial is actually counted.

--Alan